package Engine;

import java.util.Collections;
import java.util.Hashtable;
import java.util.LinkedList;

import ADT.Process;
import ADT.User;
import ADT.myQueue;
import ADT.result;

public class GIL {

	static LinkedList<User> users;
	static LinkedList<Process> processes;
	static Hashtable<Process, Character> Map;
	// Table of processes and their corresponding list of tickets, each
	// ticket represented using a different integer
	static Hashtable<Process, LinkedList<Integer>> tickets;
	static LinkedList<Integer> listOfTickets; // List of all tickets
	// that's used in getting the
	// random element
	static LinkedList<result> result;
	static myQueue queue;
	static int startTime;
	static int count;

	static Hashtable<User, myQueue> user2queue;
	static Hashtable<Process, User> process2user;
	static LinkedList<User> userOrder;

	static myQueue[] levels;

	public static void main(String[] args) throws InterruptedException {
		System.out
				.println("**************************************************************************************\nLottery Scheduling\n");
		initializeLottery();
		lottery(startTime);
		for (int i = 0; i < result.size(); i++)
			System.out.print(result.get(i) + "\n");
		System.out
				.println("**************************************************************************************\nFair Share Scheduling\n");
		initialize();
		fairShare();
		for (int i = 0; i < result.size(); i++)
			System.out.print(result.get(i) + "\n");
		System.out
				.println("**************************************************************************************\nMultilevel Feedback Scheduling\n");
		initialize();
		multilevelFeedback();
		for (int i = 0; i < result.size(); i++)
			System.out.print(result.get(i) + "\n");
		System.out
				.println("**************************************************************************************");
	}

	public static void initialize() {
		// Creating Users
		users = new LinkedList<User>();
		users.add(new User("Nader Alexan", 'l'));
		users.add(new User("Joe Aweselim", 'm'));
		users.add(new User("Omar Hassab", 'h'));

		// Creating Processes
		processes = new LinkedList<Process>();
		processes.add(new Process("Awesome", 2, 4, "Nader Alexan"));
		processes.add(new Process("Awesome2", 2, 5, "Nader Alexan"));
		processes.add(new Process("Epic", 3, 4, "Joe Aweselim"));
		processes.add(new Process("Epic2", 8, 2, "Joe Aweselim"));
		processes.add(new Process("Win", 10, 1, "Omar Hassab"));
		processes.add(new Process("Win 2", 1, 2, "Omar Hassab"));

		// A table that maps each process with it's owner's priority
		Map = new Hashtable<Process, Character>();
		// Filling Map with the data
		for (int i = 0; i < processes.size(); i++) {
			Process current = processes.get(i);
			int j;
			for (j = 0; j < users.size(); j++)
				// checks if the current process belongs to a certain user
				if (users.get(j).getName().equalsIgnoreCase(current.getUser()))
					break;
			// If the loop finished its iterations without going inside the
			// if-statement
			// then the user was not found. Print a msg. Otherwise, add the
			// process and the user's priority to the Map
			if (j == users.size())
				System.out.println("Process " + current.getName()
						+ " does not belong to any user");
			else
				Map.put(current, users.get(j).getPriority());
		}

		// Initializing the list of processes that shows which process ran at
		// which time
		result = new LinkedList<result>();

		// Checking for the lowest arrival time of processes
		startTime = (processes.size() > 0) ? processes.get(0).getArrival() : -1;
		for (int i = 0; i < processes.size(); i++)
			if (startTime > processes.get(i).getArrival())
				startTime = processes.get(i).getArrival();

		/***********************************************************/
		// Mapping each user to a queue
		user2queue = new Hashtable<User, myQueue>();
		for (int i = 0; i < users.size(); i++)
			user2queue.put(users.get(i), new myQueue());

		// Mapping each process to its corresponding user
		process2user = new Hashtable<Process, User>();
		for (int i = 0; i < processes.size(); i++) {
			Process current = processes.get(i);
			int j;
			for (j = 0; j < users.size(); j++)
				// checks if the current process belongs to a certain user
				if (users.get(j).getName().equalsIgnoreCase(current.getUser()))
					break;
			// If the loop finished its iterations without going inside the
			// if-statement
			// then the user was not found. Print a msg. Otherwise, add the
			// process and the user's priority to the Map
			if (j == users.size())
				System.out.println("Process " + current.getName()
						+ " does not belong to any user");
			else
				process2user.put(current, users.get(j));
		}
		// The order in which users will be allowed to run their processes
		userOrder = new LinkedList<User>();
	}

	public static void multilevelFeedback() {
		// Initializing the levels
		levels = new myQueue[4];
		for (int i = 0; i < levels.length; i++)
			levels[i] = new myQueue();

		// setting current time to start time
		int currentTime = startTime;

		// Loop until no processes need to run anymore
		while (!processes.isEmpty()) {
			// Check if any processes are arriving
			check4newProcessesArrivingMultilevelFeedback(currentTime);
			// If no processes need to run at the current time, then increment
			// the time
			if (allEmpty("multilevelfeedback")) {
				currentTime++;
				continue;
			}
			// Set quantums for the 4 levels
			int[] quantum = { 1, 2, 4, 8 };
			// Iterate through the 4 levels
			for (int i = 0; i < levels.length; i++) {
				// If the first level is not empty, then run the processes in it
				if (!levels[0].isEmpty())
					i = 0;
				// Go through the processes of the current level
				while (!levels[i].isEmpty()) {
					// Get the first process
					Process currentProcess = levels[i].dequeue();
					// Run the process for its assigned quantum or until it
					// finishes running, whichever is smaller
					for (int j = 0; j < quantum[i]
							&& currentProcess.getRun() > 0; j++) {
						// Run process for one time unit
						currentProcess.decRun();
						// Add process to result
						result.add(new result(currentProcess.getName(),
								currentTime));
						// Increment time
						currentTime++;
						// Check for new processes arriving and add them the
						// first level
						check4newProcessesArrivingMultilevelFeedback(currentTime);
					}
					// If the current process still needs to run then I add it
					// to the next level, unless we are at the lowest level,
					// then I just add it to the same level
					if (currentProcess.getRun() > 0)
						if (i < levels.length - 1)
							levels[i + 1].enqueue(currentProcess);
						else
							levels[i].enqueue(currentProcess);
					else
						// If process finished running, then I just remove it!
						processes.remove(currentProcess);
				}
			}
		}
	}

	// Checks if all queues/levels are empty in case at a certain time no
	// process needs to run
	private static boolean allEmpty(String type) {
		// Incase of Multilevel feedback, check all levels
		if (type.equalsIgnoreCase("multilevelfeedback")) {
			for (int i = 0; i < levels.length; i++)
				if (!levels[i].isEmpty())
					return false;
		} else
			// Incase of fair share, check all user queues
			for (int i = 0; i < users.size(); i++)
				if (!user2queue.get(users.get(i)).isEmpty())
					return false;
		return true;
	}

	// Checks if any new processes arrive at current time and adds them to the first level
	public static void check4newProcessesArrivingMultilevelFeedback(
			int currentTime) {
		// Loop through processes
		for (int i = 0; i < processes.size(); i++)
			// If this process arrives at current time, add it to the first level
			if (processes.get(i).getArrival() == currentTime)
				levels[0].enqueue(processes.get(i));
	}
	


	public static void fairShare() throws InterruptedException {
		int currentTime = startTime;
		// Check any new processes arriving
		check4newProcessesArriving(startTime);
		while (!processes.isEmpty()) {
			while (allEmpty("fairshare")) {
				currentTime++;
				check4newProcessesArriving(currentTime);
			}
			// Get the first user to use the CPU
			User currentUser = userOrder.removeFirst();
			// Add the user to the end of the queue
			userOrder.addLast(currentUser);
			// Find the time this user gets
			int CPUtime = getCPUtime(currentUser);
			Process currentProcess = null;
			// Get the user's corresponding queue of processes
			myQueue currentQueue = user2queue.get(currentUser);
			// A flag used to check if a process ran twice (the quantum)
			boolean ranTwice = true;
			// Allow the processes of the current user to run for the given CPU
			// time
			for (; CPUtime > 0; CPUtime--) {
				if (currentQueue.isEmpty())
					break;
				// Check if process finished it's quantum or doesn't need to run
				// anymore
				if (ranTwice || currentProcess.getRun() == 0) {
					currentQueue.enqueue(currentProcess);
					currentProcess = currentQueue.dequeue();
					ranTwice = false;
				}

				currentQueue.enqueue(currentProcess);
				/**
				 * Allow the curretProcess to run for one time unit and add it
				 * to the list of result
				 **/
				currentProcess.decRun();
				result
						.addLast(new result(currentProcess.getName(),
								currentTime));
				// Increment the time
				currentTime++;
				check4newProcessesArriving(currentTime);
				ranTwice = !ranTwice;
			}
		}
	}

	// Goes through all the processes and checks for any process that doesn't
	// need to run anymore, and removes it

	public static void removeFinishedProcesses() {
		for (int i = 0; i < users.size(); i++) {
			// Get current user
			User currentUser = users.get(i);
			// Get user's queue
			myQueue currentQueue = user2queue.get(currentUser);
			// Go through the queue and remove whatever process needs to be
			// removed
			if (currentQueue != null) {
				LinkedList<Integer> toBeRemoved = new LinkedList<Integer>();
				for (int j = 0; j < currentQueue.size(); j++)
					if (currentQueue.get(j).getRun() == 0)
						toBeRemoved.addLast(j);
				while (!toBeRemoved.isEmpty())
					processes.remove(currentQueue.remove(toBeRemoved
							.removeLast()));
			}
		}
	}

	// Checks for new processes arriving at the current time and adds them to
	// the queue

	public static void check4newProcessesArriving(int currentTime) {
		/**
		 * Before getting into checking for new processes, we will remove any
		 * processes that finished running
		 **/
		removeFinishedProcesses();
		// Checking if any process is arriving at the current time and adds them
		// to the queue 6f the corresponding user
		for (int i = 0; i < processes.size(); i++)
			if (processes.get(i).getArrival() == currentTime) {
				User user = process2user.get(processes.get(i));
				myQueue queue = user2queue.get(user);
				queue.enqueue(processes.get(i));
				if (!userOrder.contains(user))
					userOrder.addLast(user);
			}
	}

	// Gets the quantum for a specific process

	public static int getCPUtime(User current) {
		int result;
		switch (current.getPriority()) {
		case 'h':
			result = 6;
			break;
		case 'm':
			result = 4;
			break;
		default:
			result = 2;
			break;
		}
		return result;
	}

	public static void initializeLottery() {
		initialize();
		tickets = new Hashtable<Process, LinkedList<Integer>>();

		// representing each ticket
		int id = 1;
		listOfTickets = new LinkedList<Integer>();

		setQuantums4Lottery();

		// giving each process a list of tickets according to its
		// priority level, and adding all tickets to listOfTickets
		for (int i = 0; i < processes.size(); i++) {
			LinkedList<Integer> temp = new LinkedList<Integer>();
			for (int j = 0; j < getQuantum4Lottery(processes.get(i)); j++) {
				temp.add(id);
				listOfTickets.add(id);
				id++;
			}
			tickets.put(processes.get(i), temp);
		}
	}

	// checks if tickets given to a certain process are enough, if not it
	// increases the number of tickets given to each priority level

	public static void lottery(int currentTime) {
		try {
			// recursive case until all processes run
			if (!processes.isEmpty()) {
				if (!isAvailable(processes, currentTime)) {
					currentTime++;
					lottery(currentTime);
				} else {
					Process owner = null;
					// shuffles the list, then selecting the first ticket
					// (random selection)
					Collections.shuffle(listOfTickets);
					int i;

					// getting the owner process of the chosen ticket
					for (i = 0; i < processes.size(); i++) {
						if (tickets.get(processes.get(i)).contains(
								listOfTickets.get(0))) {
							owner = processes.get(i);
							break;
						}
					}

					// keep on calling the method until a ticket that
					// belongs to a process that has arrived is picked
					if (owner.getArrival() > currentTime) {
						lottery(currentTime);
					} else {
						result
								.addLast(new result(owner.getName(),
										currentTime));
						currentTime++;
						if (owner.getRun() == 1) {

							// after the process finishes running, remove all
							// its tickets
							listOfTickets.removeAll(tickets.get(owner));
							processes.remove(owner);
							lottery(currentTime);
						} else {
							if (owner.getRun() == 2) {
								result.addLast(new result(owner.getName(),
										currentTime));
								currentTime++;
								listOfTickets.removeAll(tickets.get(owner));
								processes.remove(owner);
								lottery(currentTime);
							} else {
								result.addLast(new result(owner.getName(),
										currentTime));
								currentTime++;
								processes.get(i).setRun(owner.getRun() - 2);
								listOfTickets.remove(listOfTickets.get(0));
								lottery(currentTime);
							}
						}
					}
				}
			} else {
				return;
			}
		} catch (IndexOutOfBoundsException e) {
			System.out.println(e.getMessage());
			System.out.println("Not enough tickets");
		}
	}

	// checks if any process is currently available

	public static void setQuantums4Lottery() {
		for (count = 1; true; count++) {
			int i;
			for (i = 0; i < processes.size(); i++) {
				Process current = processes.get(i);
				int priority = (Map.get(current) == 'h') ? 3 : (Map
						.get(current) == 'm') ? 2 : 1;
				if (priority * count < current.getRun() / 2 + current.getRun()
						% 2)
					break;
			}
			if (i == processes.size())
				break;
		}
	}
	
	public static boolean isAvailable(LinkedList<Process> processes,
			int currentTime) {
		for (int i = 0; i < processes.size(); i++) {
			if (processes.get(i).getArrival() <= currentTime)
				return true;
		}
		return false;
	}

	// calculates the number of tickets that should be given to each process

	// according to its user priority
	public static int getQuantum4Lottery(Process current) {
		int remainingTime = current.getRun();
		int result = (Map.get(current) == 'h') ? 3
				: (Map.get(current) == 'm') ? 2 : 1;
		return (remainingTime < result) ? remainingTime : (result * count);
	}
}
